package com.easy.leetcode;

import java.util.*;

/**
 * @ClassName FindSubstring30
 * @Description 30. 串联所有单词的子串
 * @Author zheng
 * @Date 2021/11/4 21:13
 * @Version 1.0
 **/
public class FindSubstring30 {
    //
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        //每个单词出现的次数
        Map<String, Integer> wordsMap = new HashMap<>();
        for (String word : words) {
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }
        //一个单词的长度
        int oneWordLength = words[0].length();
        //words数组的单词总长度
        int wordsLength = oneWordLength * words.length;
        //注意边界值
        for (int i = 0; i <= s.length() - wordsLength; i++) {
            //记录滑动窗口内 所有字符串出现的次数
            Map<String, Integer> tmpMap = new HashMap<>(wordsMap);
            for (int j = i; j < i + wordsLength; j = j + oneWordLength) {
                String tmpStr = s.substring(j, j + oneWordLength);
                if (tmpMap.getOrDefault(tmpStr, 0) == 0) {
                    break;
                } else {
                    tmpMap.put(tmpStr, tmpMap.getOrDefault(tmpStr, 0) - 1);
                }
                if (j == i + wordsLength - oneWordLength) {
                    res.add(i);
                }
            }
        }
        return res;
    }


    //
    public static List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        //每个单词出现的次数
        Map<String, Integer> wordsMap = new HashMap<>();
        for (String word : words) {
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }
        //一个单词的长度
        int oneWordLength = words[0].length();
        //words数组的单词总长度
        int wordsLength = oneWordLength * words.length;
        //滑动窗口不同的开始位置
        for (int i = 0; i < oneWordLength; i++) {
            //滑动窗口内单词出现的次数
            Map<String, Integer> tmpMap = new HashMap<>();
            //滑动窗口内已有单词个数
            int count = 0;
            //滑动窗口开始位置
            int startIndex = 0;
            //滑动窗口，每次移动一个单词
            for (int j = i; j <= s.length() - oneWordLength; j = j + oneWordLength) {
                if (j == i) {
                    startIndex = j;
                }
                //当前的单词
                String tmpStr = s.substring(j, j + oneWordLength);
                //更新滑动窗口内单词个数
                tmpMap.put(tmpStr, tmpMap.getOrDefault(tmpStr, 0) + 1);
                //count值等于 words.length - 1时，此时滑动窗口的长度与匹配的单词s长度相等
                if (count == words.length - 1) {
                    //计算当前map中的数据是否跟wordsMap一致
                    Set<Map.Entry<String, Integer>> entries = wordsMap.entrySet();
                    //循环遍历至结尾标识
                    boolean end = true;
                    for (Map.Entry<String, Integer> entry : entries) {
                        if (!entry.getValue().equals(tmpMap.get(entry.getKey()))) {
                            end = false;
                            break;
                        }
                    }
                    //循环遍历至结尾，表示未出现不一致的单词，记录索引开始位置
                    if (end) {
                        res.add(startIndex);
                    }
                    //将第一个单词，从窗口的开始位置移出
                    String first = s.substring(startIndex, startIndex + oneWordLength);
                    tmpMap.put(first, tmpMap.get(first) - 1);
                    //开始索引向后移动一个单词长度
                    startIndex += oneWordLength;
                } else {
                    count++;
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        String[] str = new String[]{"foo", "bar"};
        List lst = findSubstring1("barfoothefoobarman", str);
        System.out.println(lst.toString());
        System.out.println(str.length);
    }
}
